/**
 * Project of Vehicle Routing Problem with Time Windows implements 
 * some of well-known algorithms for solving VRPTW and presents new 
 * one.
 *
 * @author Michal Drobny  
 */

package heuristic;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import util.Pair;
import logic.destination.Destination;
import logic.evaluator.Evaluator;
import logic.restriction.enumeration.IterationType;
import logic.restrictionAdapter.RestrictionAdapter;
import logic.route.Cycle;

/**
 * Represents the Nearest inserting method for solving VRP problem.
 * 
 * @author Michal Drobny
 * @date 7.11.2014
 */
public class NearestInserting extends AbstractInsertingMethod {

	@Override
	protected Cycle addNextDestination(Cycle cycle,
			Set<Destination> unusedDestinations, Evaluator evaluator,
			RestrictionAdapter restrictionAdapter) {

		Cycle testCycle = new Cycle(cycle.getDestinations());
		for (Destination unusedDestination : getSortedListByDistance(cycle,
				unusedDestinations, evaluator)) {

			Double bestValue = Double.MAX_VALUE;
			Destination bestDestination = null;
			Cycle bestCycle = null;

			for (int i = 0; i < cycle.getDestinations().size(); ++i) {
				Destination cycleDestination = cycle.getDestinations().get(i);
				Destination cycleNextDestination = cycle.getDestinations().get(
						(i + 1) % cycle.getDestinations().size());
				testCycle.addAfter(unusedDestination, cycleDestination);
				Double currentValue = evaluator.evaluate(cycleDestination,
						unusedDestination)
						+ evaluator.evaluate(unusedDestination,
								cycleNextDestination);
				if (restrictionAdapter.canIterate(IterationType.CYCLE, testCycle)
						&& currentValue < bestValue) {
					bestValue = evaluator.evaluate(cycleDestination,
							unusedDestination);
					bestDestination = unusedDestination;
					bestCycle = new Cycle(testCycle.getDestinations());
				}

				testCycle.remove(unusedDestination);
			}

			if (bestCycle != null) {
				unusedDestinations.remove(bestDestination);
				return bestCycle;
			}
		}
		return null;
	}

	/**
	 * Gets the list of destinations (the same destinations as in set
	 * destinations), but sorted by distance to cycle destinations. It means
	 * that the first destination in result list will be the nearest destination
	 * to some destination from cycle.
	 * 
	 * @param cycle
	 *            The cycle
	 * @param destinations
	 *            The destinations
	 * @return sorted list by distance
	 */
	private List<Destination> getSortedListByDistance(Cycle cycle,
			Set<Destination> destinations, Evaluator evaluator) {

		TreeSet<DoubleDestinationPair> resultSet = new TreeSet<DoubleDestinationPair>();
		
		for (Destination destination : destinations) {
			Double minValue = Double.MAX_VALUE;
			for (Destination cycleDestination : cycle.getDestinations()) {
				Double currentValue = evaluator.evaluate(destination,
						cycleDestination);
				if (currentValue != -1 && currentValue < minValue)
					minValue = currentValue;
			}
			resultSet.add(new DoubleDestinationPair(minValue, destination));
		}
		
		Iterator<DoubleDestinationPair> iterator = resultSet.descendingIterator();
		LinkedList<Destination> resultList = new LinkedList<Destination>();
		while(iterator.hasNext()) {
			DoubleDestinationPair pair = iterator.next();
			resultList.addFirst(pair.getValue());
		}

		return resultList;
	}

	/**
	 * Helper class to represents a pair of Double and Destination.
	 * 
	 * @author Michal Drobny
	 * @date 10.11.2014
	 */
	private class DoubleDestinationPair extends Pair<Double, Destination> {

		/**
		 * Constructor.
		 * 
		 * @param key
		 *            The key
		 * @param value
		 *            The value
		 */
		public DoubleDestinationPair(Double key, Destination value) {
			super(key, value);
		}

		@Override
		public int compareTo(Pair<Double, Destination> arg0) {
			return getKey().compareTo(arg0.getKey());
		}
	}
}